# 分割等和子集
# leetcode第416题: https://leetcode.cn/problems/partition-equal-subset-sum/
# 背包问题: https://www.bilibili.com/video/BV1rt4y1N7jE
# Date: 2025/3/25
from leetcode import test_function as tf


def canPartition(nums: list[int]) -> bool:
    """背包问题
    容量为sum(nums) // 2的背包能否被装满
    """
    s = sum(nums)
    if s % 2 != 0:
        return False
    w = sum(nums) // 2

    n = len(nums)
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            if j >= nums[i - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]
            if dp[i][j] == w:  # 背包装满
                return True

    return False


def canPartition_opt(nums: list[int]) -> bool:
    """
    使用一维滚动数组代替
    """
    s = sum(nums)
    if s % 2 != 0:
        return False
    w = sum(nums) // 2

    dp = [0] * (w + 1)
    for num in nums:
        for j in range(w, num - 1, -1):
            dp[j] = max(dp[j], dp[j - num] + num)
            if dp[j] == w:
                return True

    return False


if __name__ == '__main__':
    inp = [{"nums": [1, 5, 11, 5]}, {"nums": [1, 2, 3, 5]}, {"nums": [2, 2, 3, 5]}, {"nums": [14, 9, 8, 4, 3, 2]}]
    out = [True, False, False, True]
    tf(canPartition, inp, out)
    tf(canPartition_opt, inp, out)
